home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / Tools / less-252 / search.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-05-11  |  13.1 KB  |  666 lines
  1. /*
  2.  * Copyright (c) 1984,1985,1989,1994  Mark Nudelman
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  * 1. Redistributions of source code must retain the above copyright
  9.  *    notice, this list of conditions and the following disclaimer.
  10.  * 2. Redistributions in binary form must reproduce the above copyright
  11.  *    notice in the documentation and/or other materials provided with 
  12.  *    the distribution.
  13.  *
  14.  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY
  15.  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 
  17.  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE
  18.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
  19.  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT 
  20.  * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 
  21.  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 
  22.  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE 
  23.  * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN 
  24.  * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25.  */
  26.  
  27.  
  28. /*
  29.  * Routines to search a file for a pattern.
  30.  */
  31.  
  32. #include "less.h"
  33. #include "position.h"
  34.  
  35. #if HAVE_POSIX_REGCOMP
  36. #include <regex.h>
  37. #endif
  38. #if HAVE_RE_COMP
  39. char *re_comp();
  40. int re_exec();
  41. #endif
  42. #if HAVE_REGCMP
  43. char *regcmp();
  44. char *regex();
  45. extern char *__loc1;
  46. #endif
  47. #if HAVE_V8_REGCOMP
  48. #include "regexp.h"
  49. #endif
  50. #if NO_REGEX
  51. static int match();
  52. #endif
  53.  
  54. extern int sigs;
  55. extern int how_search;
  56. extern int caseless;
  57. extern int linenums;
  58. extern int jump_sline;
  59. extern int bs_mode;
  60. #if HILITE_SEARCH
  61. extern int hilite_search;
  62. extern int screen_trashed;
  63. #endif
  64.  
  65. /*
  66.  * These are the static variables that represent the "remembered"
  67.  * search pattern.  
  68.  */
  69. #if HAVE_POSIX_REGCOMP
  70. static regex_t *regpattern = NULL;
  71. #endif
  72. #if HAVE_RE_COMP
  73. int re_pattern = 0;
  74. #endif
  75. #if HAVE_REGCMP
  76. static char *cpattern = NULL;
  77. #endif
  78. #if HAVE_V8_REGCOMP
  79. static struct regexp *regpattern = NULL;
  80. #endif
  81. #if NO_REGEX
  82. static char *last_pattern = NULL;
  83. #endif
  84.  
  85. static int is_caseless;
  86. static int is_ucase_pattern;
  87. #if HILITE_SEARCH
  88. static int no_hilite_search;
  89. #endif
  90.  
  91. /*
  92.  * Convert text.  Perform one or more of these transformations:
  93.  */
  94. #define    CVT_TO_LC    01    /* Convert upper-case to lower-case */
  95. #define    CVT_BS        02    /* Do backspace processing */
  96.  
  97.     static void
  98. cvt_text(odst, osrc, ops)
  99.     char *odst;
  100.     char *osrc;
  101.     int ops;
  102. {
  103.     register char *dst;
  104.     register char *src;
  105.  
  106.     for (src = osrc, dst = odst;  *src != '\0';  src++, dst++)
  107.     {
  108.         if ((ops & CVT_TO_LC) && isupper(*src))
  109.             /* Convert uppercase to lowercase. */
  110.             *dst = tolower(*src);
  111.         else if ((ops & CVT_BS) && *src == '\b' && dst > odst)
  112.             /* Delete BS and preceding char. */
  113.             dst -= 2;
  114.         else 
  115.             /* Just copy. */
  116.             *dst = *src;
  117.     }
  118.     *dst = '\0';
  119. }
  120.  
  121. /*
  122.  * Are there any uppercase letters in this string?
  123.  */
  124.     static int
  125. is_ucase(s)
  126.     char *s;
  127. {
  128.     register char *p;
  129.  
  130.     for (p = s;  *p != '\0';  p++)
  131.         if (isupper(*p))
  132.             return (1);
  133.     return (0);
  134. }
  135.  
  136. /*
  137.  * Is there a previous (remembered) search pattern?
  138.  */
  139.     static int
  140. prev_pattern()
  141. {
  142. #if HAVE_POSIX_REGCOMP
  143.     return (regpattern != NULL);
  144. #endif
  145. #if HAVE_RE_COMP
  146.     return (re_pattern != 0);
  147. #endif
  148. #if HAVE_REGCMP
  149.     return (cpattern != NULL);
  150. #endif
  151. #if HAVE_V8_REGCOMP
  152.     return (regpattern != NULL);
  153. #endif
  154. #if NO_REGEX
  155.     return (last_pattern != NULL);
  156. #endif
  157. }
  158.  
  159. /*
  160.  * Undo search string highlighting.
  161.  */
  162.     public void
  163. undo_search()
  164. {
  165.     if (!prev_pattern())
  166.     {
  167.         error("No previous regular expression", NULL_PARG);
  168.         return;
  169.     }
  170. #if HILITE_SEARCH
  171.     no_hilite_search = !no_hilite_search;
  172.     screen_trashed = 1;
  173. #endif
  174. }
  175.  
  176. /*
  177.  * Compile a pattern in preparation for a pattern match.
  178.  */
  179.     static int
  180. compile_pattern(pattern)
  181.     char *pattern;
  182. {
  183. #if HAVE_POSIX_REGCOMP
  184.     regex_t *s = (regex_t *) ecalloc(1, sizeof(regex_t));
  185.     if (regcomp(s, pattern, 0))
  186.     {
  187.         free(s);
  188.         error("Invalid pattern", NULL_PARG);
  189.         return (-1);
  190.     }
  191.     if (regpattern != NULL)
  192.         regfree(regpattern);
  193.     regpattern = s;
  194. #endif
  195. #if HAVE_RE_COMP
  196.     PARG parg;
  197.     if ((parg.p_string = re_comp(pattern)) != NULL)
  198.     {
  199.         error("%s", &parg);
  200.         return (-1);
  201.     }
  202.     re_pattern = 1;
  203. #endif
  204. #if HAVE_REGCMP
  205.     char *s;
  206.     if ((s = regcmp(pattern, 0)) == NULL)
  207.     {
  208.         error("Invalid pattern", NULL_PARG);
  209.         return (-1);
  210.     }
  211.     if (cpattern != NULL)
  212.         free(cpattern);
  213.     cpattern = s;
  214. #endif
  215. #if HAVE_V8_REGCOMP
  216.     struct regexp *s;
  217.     if ((s = regcomp(pattern)) == NULL)
  218.     {
  219.         /*
  220.          * regcomp has already printed error message via regerror().
  221.          */
  222.         return (-1);
  223.     }
  224.     if (regpattern != NULL)
  225.         free(regpattern);
  226.     regpattern = s;
  227. #endif
  228. #if NO_REGEX
  229.     static char lpbuf[100];
  230.     strcpy(lpbuf, pattern);
  231.     last_pattern = lpbuf;
  232. #endif
  233.     return (0);
  234. }
  235.  
  236. /*
  237.  * Perform a pattern match with the previously compiled pattern.
  238.  */
  239.     static int
  240. match_pattern(line)
  241.     char *line;
  242. {
  243. #if HAVE_POSIX_REGCOMP
  244.     return (!regexec(regpattern, line, 0, NULL, 0));
  245. #endif
  246. #if HAVE_RE_COMP
  247.     return (re_exec(line) == 1);
  248. #endif
  249. #if HAVE_REGCMP
  250.     return (regex(cpattern, line) != NULL);
  251. #endif
  252. #if HAVE_V8_REGCOMP
  253.     return (regexec(regpattern, line));
  254. #endif
  255. #if NO_REGEX
  256.     return (match(last_pattern, line, (char*)NULL, (char*)NULL));
  257. #endif
  258. }
  259.  
  260. /*
  261.  * Change the caseless-ness of searches.  
  262.  * Updates the internal search state to reflect a change in the -i flag.
  263.  */
  264.     public void
  265. chg_caseless()
  266. {
  267.     if (!is_ucase_pattern)
  268.         is_caseless = caseless;
  269. }
  270.  
  271. /*
  272.  * Figure out where to start a search.
  273.  */
  274.     static POSITION
  275. search_pos(goforw)
  276.     int goforw;
  277. {
  278.     POSITION pos;
  279.     int linenum;
  280.  
  281.     if (empty_screen())
  282.     {
  283.         /*
  284.          * Start at the beginning (or end) of the file.
  285.          * (The empty_screen() case is mainly for 
  286.          * command line initiated searches;
  287.          * for example, "+/xyz" on the command line.)
  288.          */
  289.         if (goforw)
  290.         {
  291.             return (ch_zero());
  292.         } else
  293.         {
  294.             pos = ch_length();
  295.             if (pos == NULL_POSITION)
  296.                 return (ch_zero());
  297.             return (pos);
  298.         }
  299.     }
  300.     if (how_search)
  301.     {
  302.         /*
  303.          * Search does not include current screen.
  304.          */
  305.         if (goforw)
  306.             linenum = BOTTOM_PLUS_ONE;
  307.         else
  308.             linenum = TOP;
  309.         pos = position(linenum);
  310.     } else
  311.     {
  312.         /*
  313.          * Search includes current screen.
  314.          * It starts at the jump target (if searching backwards),
  315.          * or at the jump target plus one (if forwards).
  316.          */
  317.         linenum = adjsline(jump_sline);
  318.         pos = position(linenum);
  319.         if (goforw)
  320.             pos = forw_raw_line(pos, (char **)NULL);
  321.     }
  322.     return (pos);
  323. }
  324.  
  325. /*
  326.  * Search for the n-th occurrence of a specified pattern, 
  327.  * either forward or backward.
  328.  * Return the number of matches not yet found in this file
  329.  * (that is, n minus the number of matches found).
  330.  * Return -1 if the search should be aborted.
  331.  * Caller may continue the search in another file 
  332.  * if less than n matches are found in this file.
  333.  */
  334.     public int
  335. search(search_type, pattern, n)
  336.     int search_type;
  337.     char *pattern;
  338.     int n;
  339. {
  340.     POSITION pos, linepos, oldpos;
  341.     register int goforw;
  342.     register int want_match;
  343.     char *line;
  344.     int linenum;
  345.     int line_match;
  346.  
  347.     /*
  348.      * Extract flags and type of search.
  349.      */
  350.     goforw = (SRCH_DIR(search_type) == SRCH_FORW);
  351.     want_match = !(search_type & SRCH_NOMATCH);
  352.  
  353.     if (pattern == NULL || *pattern == '\0')
  354.     {
  355.         /*
  356.          * A null pattern means use the previously compiled pattern.
  357.          */
  358.         if (!prev_pattern())
  359.         {
  360.             error("No previous regular expression", NULL_PARG);
  361.             return (-1);
  362.         }
  363.     } else
  364.     {
  365.         /*
  366.          * Ignore case if -i is set AND 
  367.          * the pattern is all lowercase.
  368.          */
  369.         is_ucase_pattern = is_ucase(pattern);
  370.         if (is_ucase_pattern)
  371.             is_caseless = 0;
  372.         else
  373.             is_caseless = caseless;
  374.  
  375.         /*
  376.          * Compile the pattern.
  377.          */
  378.         if (compile_pattern(pattern) < 0)
  379.             return (-1);
  380. #if HILITE_SEARCH
  381.         /*
  382.          * If our current screen *might be* displaying highlighted
  383.          * search targets, we need to repaint.
  384.          */
  385.         if (hilite_search)
  386.             screen_trashed = 1;
  387. #endif
  388.     }
  389.  
  390.     /*
  391.      * Figure out where to start the search.
  392.      */
  393.     pos = search_pos(goforw);
  394.     if (pos == NULL_POSITION)
  395.     {
  396.         /*
  397.          * Can't find anyplace to start searching from.
  398.          */
  399.         if (search_type & SRCH_PAST_EOF)
  400.             return (n);
  401.         error("Nothing to search", NULL_PARG);
  402.         return (-1);
  403.     }
  404.  
  405. #if HILITE_SEARCH
  406.     if (no_hilite_search)
  407.         screen_trashed = 1;
  408.     no_hilite_search = 0;
  409. #endif
  410.  
  411.     linenum = find_linenum(pos);
  412.     oldpos = pos;
  413.     for (;;)
  414.     {
  415.         /*
  416.          * Get lines until we find a matching one or 
  417.          * until we hit end-of-file (or beginning-of-file 
  418.          * if we're going backwards).
  419.          */
  420.         if (ABORT_SIGS())
  421.             /*
  422.              * A signal aborts the search.
  423.              */
  424.             return (-1);
  425.  
  426.         if (goforw)
  427.         {
  428.             /*
  429.              * Read the next line, and save the 
  430.              * starting position of that line in linepos.
  431.              */
  432.             linepos = pos;
  433.             pos = forw_raw_line(pos, &line);
  434.             if (linenum != 0)
  435.                 linenum++;
  436.         } else
  437.         {
  438.             /*
  439.              * Read the previous line and save the
  440.              * starting position of that line in linepos.
  441.              */
  442.             pos = back_raw_line(pos, &line);
  443.             linepos = pos;
  444.             if (linenum != 0)
  445.                 linenum--;
  446.         }
  447.  
  448.         if (pos == NULL_POSITION)
  449.         {
  450.             /*
  451.              * We hit EOF/BOF without a match.
  452.              */
  453.             return (n);
  454.         }
  455.  
  456.         /*
  457.          * If we're using line numbers, we might as well
  458.          * remember the information we have now (the position
  459.          * and line number of the current line).
  460.          * Don't do it for every line because it slows down
  461.          * the search.  Remember the line number only if
  462.          * we're "far" from the last place we remembered it.
  463.          */
  464.         if (linenums && abs((int)(pos - oldpos)) > 1024)
  465.         {
  466.             add_lnum(linenum, pos);
  467.             oldpos = pos;
  468.         }
  469.  
  470.         if (is_caseless || bs_mode == BS_SPECIAL)
  471.         {
  472.             int ops = 0;
  473.             if (is_caseless) 
  474.                 ops |= CVT_TO_LC;
  475.             if (bs_mode == BS_SPECIAL)
  476.                 ops |= CVT_BS;
  477.             cvt_text(line, line, ops);
  478.         }
  479.  
  480.         /*
  481.          * Test the next line to see if we have a match.
  482.          * We are successful if want_match and line_match are
  483.          * both true (want a match and got it),
  484.          * or both false (want a non-match and got it).
  485.          */
  486.         line_match = match_pattern(line);
  487.         if (((want_match && line_match) || (!want_match && !line_match)) &&
  488.               --n <= 0)
  489.             /*
  490.              * Found the line.
  491.              */
  492.             break;
  493.     }
  494.  
  495.     jump_loc(linepos, jump_sline);
  496.     return (0);
  497. }
  498.  
  499. #if HILITE_SEARCH
  500. /*
  501.  * Search for all occurrences of the previous pattern
  502.  * within a line.  Mark all matches found.
  503.  * "Marking" a match is done by copying "marker" into the chars whose
  504.  * positions in the "found" string are equal to the positions of
  505.  * the matching string in the "line" string.
  506.  */
  507.     public void
  508. hlsearch(line, found, marker)
  509.     char *line;
  510.     char *found;
  511.     int marker;
  512. {
  513.     char *buf;
  514.     register char *p;
  515.  
  516.     if (!prev_pattern())
  517.         return;
  518.     if (no_hilite_search)
  519.         return;
  520.  
  521.     /*
  522.      * If the last search was caseless, convert 
  523.      * uppercase from the input line to lowercase
  524.      * in a temporary buffer.
  525.      */
  526.     buf = line;
  527.     if (is_caseless)
  528.     {
  529.         /*
  530.          * {{ Yikes, a calloc for every line displayed (with -i)!
  531.          *    Is this worth optimizing? }}
  532.          */
  533.         buf = save(line);
  534.         cvt_text(buf, line, CVT_TO_LC);
  535.     }
  536.  
  537.     {
  538.         /*
  539.          * Now depending on what type of pattern matching function
  540.          * we have, define the macro NEXT_MATCH(p).
  541.          * This will look for the first match in "p";
  542.          * if it finds one it sets sp and ep to the start and 
  543.          * end of the matching string and returns 1.
  544.          * If there is no match, it returns 0.
  545.          */
  546.  
  547. #if HAVE_POSIX_REGCOMP
  548. regmatch_t rm;
  549. #define    NEXT_MATCH(p)    (!regexec(regpattern,p,1,&rm,0))
  550. #define    sp        (p+rm.rm_so)
  551. #define    ep        (p+rm.rm_eo)
  552. #endif
  553.  
  554. #if HAVE_RE_COMP
  555. @@@ Sorry, re_comp does not support HILITE_SEARCH.
  556. @@@ Either undefine HILITE_SEARCH, or use the regexp.c that is 
  557. @@@ distributed with "less" (and set HAVE_V8_REGCOMP).
  558. #endif
  559.  
  560. #if HAVE_REGCMP
  561. #define    sp        __loc1
  562. char *ep;
  563. #define    NEXT_MATCH(p)    (ep = regex(cpattern, p))
  564. #endif
  565.  
  566. #if HAVE_V8_REGCOMP
  567. #define    sp        (regpattern->startp[0])
  568. #define    ep        (regpattern->endp[0])
  569. #define    NEXT_MATCH(p)    (regexec(regpattern, p))
  570. #endif
  571.  
  572. #if NO_REGEX
  573. char *sp, *ep;
  574. #define    NEXT_MATCH(p)    (match(last_pattern,p,&sp,&ep))
  575. #endif
  576.  
  577.         for (p = buf;  NEXT_MATCH(p);  )
  578.         {
  579.             register char *fsp = &found[sp-buf];
  580.             register char *fep = &found[ep-buf];
  581.  
  582.             while (fsp < fep)
  583.                 *fsp++ = marker;
  584.             
  585.             /*
  586.              * Move past current match to see if there
  587.              * are any more matches.  (But don't loop 
  588.              * forever if we matched zero characters.)
  589.              */
  590.             if (ep > p)
  591.                 p = ep;
  592.             else if (*p != '\0')
  593.                 p++;
  594.             else
  595.                 break;
  596.         }
  597.     }
  598.  
  599.     if (buf != line)
  600.         free(buf);
  601. }
  602. #endif /* HILITE_SEARCH */
  603.  
  604. #if NO_REGEX
  605. /*
  606.  * We have no pattern matching function from the library.
  607.  * We use this function to do simple pattern matching.
  608.  * It supports no metacharacters like *, etc.
  609.  */
  610.     static int
  611. match(pattern, buf, pfound, pend)
  612.     char *pattern, *buf;
  613.     char **pfound, **pend;
  614. {
  615.     register char *pp, *lp;
  616.  
  617.     for ( ;  *buf != '\0';  buf++)
  618.     {
  619.         for (pp = pattern, lp = buf;  *pp == *lp;  pp++, lp++)
  620.             if (*pp == '\0' || *lp == '\0')
  621.                 break;
  622.         if (*pp == '\0')
  623.         {
  624.             if (pfound != NULL)
  625.                 *pfound = buf;
  626.             if (pend != NULL)
  627.                 *pend = lp;
  628.             return (1);
  629.         }
  630.     }
  631.     return (0);
  632. }
  633. #endif
  634.  
  635. #if HAVE_V8_REGCOMP
  636. /*
  637.  * This function is called by the V8 regcomp to report 
  638.  * errors in regular expressions.
  639.  */
  640.     void 
  641. regerror(s) 
  642.     char *s; 
  643. {
  644.     error(s, NULL_PARG);
  645. }
  646. #endif
  647.  
  648. #if !HAVE_STRCHR
  649. /*
  650.  * strchr is used by regexp.c.
  651.  */
  652.     char *
  653. strchr(s, c)
  654.     char *s;
  655.     int c;
  656. {
  657.     for ( ;  *s != '\0';  s++)
  658.         if (*s == c)
  659.             return (s);
  660.     if (c == '\0')
  661.         return (s);
  662.     return (NULL);
  663. }
  664. #endif
  665.  
  666.